package com.example.lettcode._20240910;

import java.util.Arrays;

/*
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 */
public class Di_yi_ge_pi_pei_de_xia_biao {

    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "ll";
        int i = strStr3(haystack, needle);
        System.out.println(i);
    }

    /*
        使用String的api
     */
    public static int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /*
        暴力遍历查询
     */
    public static int strStr2(String haystack, String needle) {
        int firstIndex = 0;
        int needleCount = 0;
        for (int i = 0; i < haystack.length(); i++) {
            char oldChar = haystack.charAt(i);
            for (; needleCount <= needle.length(); ) {
                char newChar = needle.charAt(needleCount);
                if (newChar != oldChar) {
                    firstIndex = 0;
                    needleCount = 0;
                    break;
                } else {
                    if (firstIndex == 0) {
                        firstIndex = i;
                        if (++needleCount == needle.length()) {
                            break;
                        }
                        break;
                    }
                }
            }
            if (needleCount == needle.length() -1 ) {
                break;
            }
        }

        return needleCount == needle.length() - 1 ? firstIndex : 0;
    }


    /*
       暴力遍历查询
    */
    public static int strStr3(String haystack, String needle) {
        // 长度不相等，直接结束
        if (haystack.length() < needle.length()) {
            return -1;
        }
        int firstIndex = -1;
        // 遍历haystack
        for (int i = 0; i < haystack.length(); i++) {
            int m = needle.length();
            int n = 0;
            // 每当haystack中的值与needle的第一个相等时，则再次遍历两个String
            while (n < m && haystack.charAt(i) == needle.charAt(0)) {
                // 记录此时的下标值
                firstIndex = i;
                // 依次比较两个String中的字符
                if (haystack.charAt(i + n) == needle.charAt(n)) {
                    // 相等则记录
                    n++;
                } else {
                    // 不相等，则遍历haystack的下一个
                    break;
                }
            }
            if (n == needle.length() ) {
                // 如果相等的记录值 等于 needle的长度，表明已经找到了数据，则直接结束
                break;
            } else if (haystack.length() - i <= needle.length()){
                // 如果不等，并且haystack中剩余的长度比needle的长度要小了，直接结束
                firstIndex = -1;
                break;
            } else {
                // 不相等，且长度够，则再次遍历haystack的的下一个
                firstIndex = -1;
            }
        }

        return firstIndex;
    }
}
